This invention relates generally to systems for providing directions to travelers and more specifically to systems for determining a route and presenting navigational instructions therefor.
Recent years have seen a rapid proliferation of devices that provide mobile access to electronic information, such as handheld computers, pagers and data-enabled cellular telephones. One compelling property of such handheld devices is their capacity to organize information dynamically according to the relative physical locations of the user, points of interest to the user, and available navigable pathways of various kinds. However, these devices do not determine a route between specified physical locations and do not present navigational instructions for traversing the route.
Related patents include the following. U.S. Pat. No. 6,047,236 xe2x80x9cGEOGRAPHIC LOCATION REFERENCING SYSTEM AND METHODxe2x80x9d discloses an addressing scheme that allows physical locations to be globally uniquely addressed and specified, including via automatic position acquisition using a global positioning system. However, it does not include the generation and presentation of navigational directions.
U.S. Pat. No. 6,038,509 xe2x80x9cSYSTEM FOR RECALCULATING A PATHxe2x80x9d discloses the use of caching to accelerate recalculation of directions when deviation from an originally prescribed path occurs. U.S. Pat. No. 6,016,485 xe2x80x9cSYSTEM FOR PATHFINDINGxe2x80x9d discloses the use of pre-computed sub-paths to accelerate the computation of minimal-cost routes in a network.
U.S. Pat. No. 6,026,384 xe2x80x9cCOST ZONESxe2x80x9d discloses a technique for determining and displaying which destinations on a digital map have distances from a given location that are within a fixed cost according to a chosen cost function. However, it does not disclose the generation or presentation of navigational directions, either to destinations within the cost zone or otherwise.
U.S. Pat. No. 6,009,403 xe2x80x9cTRAVEL PLAN PREPARING DEVICExe2x80x9d discloses a system for describing a kind of service and receiving information about areas near a travel route in which such service locations exist. A particular area can be specified, and the kinds of services available in that area are subsequently described. However, it does not disclose the generation or presentation of navigational directions that satisfy particular criteria.
U.S. Pat. No. 5,978,730 xe2x80x9cCACHING FOR PATHFINDING COMPUTATIONxe2x80x9d discloses the background execution of a path-finding algorithm without instigation by a user, such that a pre-loaded cache of data and routes relevant to a routing request are available whenever the request is made. It further discloses a particular method, using Dijkstra""s algorithm, for determining directions in a graph representing a map. The graph representation disclosed includes vertices that correspond to individual traversable segments conjoining pathway intersections, such that the vertices of the graph representation do not correspond to entire contiguous traversable pathways that potentially span multiple intersections, and such that every such intersection is not represented as an edge incident to the pathway""s vertex.
U.S. Pat. No. 5,944,769 xe2x80x9cINTERACTIVE NETWORK DIRECTORY SERVICE WITH INTEGRATED MAPS AND DIRECTIONSxe2x80x9d discloses a networkbased system to communicate directory information with corresponding locale data, and discloses direction-finding functionality.
U.S. Pat. No. 4,954,958 xe2x80x9cDIRECTIONAL INFORMATION SYSTEMxe2x80x9d discloses related functionality.
Related commercial products include services from Kivera, a company that licenses location-based services to network access providers for mobile devices. One service is direction-finding.
The invention provides a system for determining a route and presenting navigational instructions therefor. The invention in one aspect enables a user to obtain instructions for travelling from any one selected location on a particular geophysical grid to any other location via real-world means of transit. Although the invention does not restrict utilization to a particular medium of computation, an embodiment includes a computation module as part of a client application resident on a handheld device having at least one locally cached database of geospatial information. The user may specify a source location (e.g., his or her current location) to the device. Additionally or alternately, the source location may be acquired automatically via global positioning technology. The computation module may alternatively be part of a remote server that receives a request from a handheld device that is wirelessly networked to the server.
Once the computation module receives the source location information and destination location information, the computation module dynamically determines a route between the source location and the destination location. The determination of the route preferably balances descriptive simplicity of the route with a minimal total distance traversed along the route. Prior art systems optimize for distance, time or simplicity individually but not in combination.
Once the route has been determined, a presentation module of the computation module provides a natural language description of the actions the user must take to follow the route. The available pathways may include one- and two-way streets, subway systems, bus routes, overland railways and/or any other form of transit. The instructions may be tailored to users who are on foot or in vehicles, and they may be enhanced with information directed to known characteristics of the user. For example, the presentation module may instruct the user to pass by or turn at specific apparent landmarks that are likely to be of interest to him or her.
In an embodiment, the system includes a plurality of map records including a plurality of business records each identifying a business, a plurality of street records each identifying a street, and a plurality of node records each identifying a node. As used herein, a xe2x80x9cnodexe2x80x9d is defined as any uniquely specified location where traversable pathways coincide, a xe2x80x9cbusinessxe2x80x9d is defined as any physical location represented in the system that a user might want to obtain information about, and a xe2x80x9cstreetxe2x80x9d is defined as any contiguously traversable pathway via which a person can move among a set of nodes on which the pathway is incident. The business records, street records, and node records are preferably maintained in a business database, a street database, and a node database, respectively.
The system preferably further includes a computation module that can access the map records and execute an algorithm for determining a route between a source location and a destination location using at least one of the map records. The computation module can receive source location information and use it to identify the source location, and can receive destination location information and use it to identify the destination location. The computation module determines a set of source streets associated with the source location and a set of destination streets associated with the destination location. The route between the source location and the destination location, as determined by the computation module, includes a desired solution path between a source street in the set of source streets and a destination street in the set of destination streets, as determined by the algorithm. The algorithm can be biased to discover, when multiple simplest paths exist, that simplest path which traverses the minimum physical distance. Therefore, when at least two of a plurality of possible routes between the source location and the destination location are the simplest routes (i.e., both require an identical minimum number of street changes), the algorithm preferably is biased toward determining the physically shortest route (i.e., the route traversing the minimum physical distance) of the at least two possible routes.
The system preferably further includes a presentation module adapted to generate and present navigational instructions for traversing the route. In one aspect, the presentation module interprets the route, as determined by the computation module, into natural language navigational instructions that may be tailored using at least one of demographic information pertaining to the user, a preference of the user, a characteristic of the user, a characteristic of a handheld device being used by the user, information stored in the handheld device, and a characteristic of one of the businesses, one of the streets, and/or one of the nodes.
The computation module can preferably be adapted to interact with the user while executing the algorithm. For example, the computation module may provide status updates to the user to indicate that the route determination is proceeding correctly, and may temporarily suspend the algorithm to execute an interface routine that checks for user requests (e.g., to cancel the determination of the route).